1. Field of the Invention
This invention relates generally to communications networks, and more particularly to a method of distributing communication loads over multiple alternative paths.
2. Discussion of the Related Art
In an internet, several networks are connected together through the use of gateways and an internetworking protocol. The gateways (often called routers) using the protocol hide the underlying details of the actual networks in order to provide uniform service across the network. TCP/IP is a leading protocol suite for communicating across interconnected networks. "TCP" stands for transmission control protocol, a connection-oriented transport service, while "IP" stands for internet protocol, a connectionless-mode network service.
A connectionless-mode network protocol is typically packet-based. When some entity on the network wishes to send data, it sends that data as a series of packets ("packet" refers to data transmitted in discrete parts, and includes what is known in this art as "packets," "cells," "datagrams" and the like). Associated with each packet is an address indicating where the packet should be delivered. The address may be a unique Media Access Control address ("MAC address") assigned to the station to which the packet will be delivered. An IP packet encapsulates the data and other information necessary to deliver the packet to the IP entity at the destination. The destination IP entity receives the packet, strips off the data, and passes it up to an appropriate upper-layer protocol for processing. See M. Rose "The Simple Book--An Introduction to Management of TCP/IP-Internets," Prentice Hall, 1991.
More recently, there has been a move toward switched networks which provide a connection-oriented service. A discussion of how "virtual connections" may be established in a switched network and how a "best" connection path may be determined is discussed, based on the disclosure in U.S. Pat. No. 5,521,910 which issued May 28, 1996 to W. Matthews, entitled "Network Having Secure Fast Packet Switching And Guaranteed Quality of Service," which is hereby incorporated by reference in its entirety. While the invention is discussed in this context it is not intended to be limiting.
For example, FIG. 1 shows a fully meshed network topology having six Secure Fast Packet Switches (SFPS) labeled S1-S6; each switch is directly connected by a link L (also referred to as an "edge," or "arc"). In FIG. 1, each SFPS switch has four ports: some ports are labeled A for Access, and some are labeled N for Network. Access ports are attached to, for example, end users at a work station, and provide network access security and connection services. Network ports are attached to a communication device which groups a number of users together; these ports need not perform security services since this function has already been performed at the entry (access) port. The end systems, labeled "M.sub.-- ", are connected to the switches by links L. One of the end systems M10 is a network management server (NMS) which includes an SFPS switch directory and path server.
The following procedure may be followed when source M11 transmits a packet to destination M99:
1. Access switch S1 receives the packet (from M11) on inbound port A1. PA1 2. S1 looks up in its internal connection table to determine if a valid connection (M11 to M99 mapping) exists. PA1 3. As no connection is yet defined, S1 initiates a message exchange to the SFPS server (M10):
a. Switch S1 sends a message asking if M11 is allowed to talk to M99. This is where security, policy, and administrative constraints are applied. PA2 b. If the two stations M11 and M99 are allowed to have a connection, then the server M10 determines a path of switches to provide a connection between M11 and M99. PA2 c. Since M11 can reach M99 by two different paths, one "best path" is selected. "Best" is determined by, for example, cost, bandwidth, policy, loss and other metrics. A discussion of how this determination may be made is set forth below. PA2 d. Assume the best path chosen traverses S1 to S3 to S5. Server M10 then "programs" each of these switches to support this connection path.
In the above example, the protocol is "transparent" in the M11-M99 interaction--it does not modify the packets being exchanged. In contrast, traditional switches place a connection-identifier in each packet, which is remapped at each switch, to allow the packet to be switched along the path. Here, however, SFPS treats the source medium access control (MAC) address and the destination MAC address, already present in the packet, as a unique "connection-identifier" and thus the packet need not be modified.
In this example, each switch on the path has an internal connection table with the following entries:
______________________________________ Source Switch Port Source MAC Destination MAC Out Port ______________________________________ S1 A1 M11 M99 N2 S3 N1 M11 M99 N3 S5 N2 M11 M99 A2 ______________________________________
Once all of the switches are programmed (through, for example, the Simple Network Management Protocol), the packet from M11 destined for M99, i.e.:
______________________________________ Destination Address Source Address Data ______________________________________ M99 M11 Packet date ______________________________________ may be "switched" along the path as follows: M11 .fwdarw. A1S1-N2 .fwdarw. N1S3-N3 .fwdarw. N2S5-A2 .fwdarw. M99
Note that once the switches have these connections defined, subsequent packets traverse M11 to M99 without requiring any additional call setup or network management interaction. This provides fast packet switching between the end systems. Note, the M11 to M99 packet exchange occurs as if they were directly connected on the same LAN segment. Thus, a "virtual LAN" is provided, as well as transparent switching.
At each switch on the path, the switch reads from the packet the source and destination MAC addresses and combines them with the inbound (source) port on which the packet is received to form the connection-identifier. If this connection is in the switch's internal connection table, the packet will be forwarded (switched) out of the designated output port according to the corresponding entry in the table. All subsequent M11 to M99 packets will take the same path through the switches. These "virtual connections" exist until they are explicitly removed by the network management system. Thus, once a path is set up, it remains in place regardless of network activity or actual connectivity unless the path is reprogrammed.
Current LAN (local area network) switching technologies do not use link utilization knowledge, or any other metric which varies in response to how the network is being used, to select among alternative paths between pairs of sources and destinations of communication traffic. In a mesh network, the shortest path between a source and destination is the path that involves the fewest number of arcs and nodes between the source and destination. In other words, a path which traverses two nodes is shorter than a path which traverses three nodes. In some instances a fixed cost is assigned to each link. Cost can be any administratively assigned value which helps to differentiate between multiple paths. For example, the cost may be a weighting factor which differentiates between paths based on how long it will take to start a transmission on a particular arc of a path.
Because current strategies use a fixed cost associated with each link, current technologies pick the shortest path or the path with the least cost between a source and destination and continuously use that path for all traffic until some component of that path becomes disabled, and then selects an alternative path. Thus, every connection from source "A" to destination "B" will be routed through the same path. Once the shortest or least costly path is selected, no other alternative paths are considered--for this or any other connection between A and B. The selected path is used over and over again until all of the bandwidth of the path is being used. Alternative paths are ignored until the shortest path is no longer viable. This causes some path components to become congested, and in extreme cases, to fail.
In sum, when the instantaneous load of the network is unbalanced because a majority of the traffic is between a small number of sources and destinations, the network becomes heavily congested along the preferred paths between those sources and destinations. When alternative paths do exist, they are not utilized, and the network operates much less efficiently than it could.
It would thus be desirable to provide a method of distributing a communication load over multiple alternative paths in order to improve network efficiency.